Operators use different middlebox services or appliances, called inline services, such as deep packet inspection (DPI), logging/metering/charging/advanced charging, firewall (FW), virus scanning (VS), intrusion detection and prevention (IDP), network address translation (NAT), etc., to manage subscribers' traffic. These services have high requirements on throughput and packet inspection capabilities. They can be transparent or nontransparent to the end users. Inline services can be hosted in dedicated physical hardware, or in virtual machines.
Service chaining is required if the traffic needs to go through more than one inline service. Moreover, if more than one chain of services is possible, then the operator needs to configure the networking infrastructure to direct the right traffic through the right inline service path. In this specification, traffic steering refers to leading the traffic through the right inline service path.
There have been some efforts to determine how to steer traffic to provide inline service chaining. The mechanisms developed through those efforts generally are designed to explicitly insert the inline services on the path between end-points, or explicitly route traffic through different middleboxes according to policies. These mechanisms only provide suboptimal performance within a network in connecting services to the network. While the prior co-pending patent applications cited above aim at routing in a network where the order of services is predetermined, and embodiments of this invention aim at determining optimal locations for placing services where the subscribers do not have to be served by services with a predetermined order.